package src.greed;

import java.util.Arrays;
import java.util.Comparator;

public class no452 {//用最少数量的弓箭射气球

    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) return 0;
        //按照左边界排序 升序
        //Arrays.sort(points, (a,b)->a[0]-b[0]);
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));  //使用Integer内置比较方法，不会溢出
        int count = 1;  //至少需要一支箭
        for (int i = 1; i < points.length; i++) {
            //左边界 > 右边界时，即不重叠需要多一支
            if (points[i][0] > points[i - 1][1]) {
                count++;
            } else {
                //左边界 <= 右边界时，不用count++，更新右边界为更小的一个，和下一个比较
                points[i][1] = Math.min(points[i][1], points[i - 1][1]);
            }
        }
        return count;

    }

}
